Sudoku solver

Time: O((9!)^9); Space: O(1); hard

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.

  2. Each of the digits 1-9 must occur exactly once in each column.

  3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character ‘.’.

A sudoku puzzle…

…and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9 and the character ‘.’.

  • You may assume that the given Sudoku puzzle will have a single unique solution.

  • The given board size is always 9x9.

[1]:

class Solution1(object):
    """
    Do not return anything, modify board in-place instead.
    Time: ((9!)^9)
    Space: (1)
    """
    def solveSudoku(self, board):
        """
        :type board: List[List[str]], 9x9 2D array
        :rtype: None
        """
        def isValid(board, x, y):

            for i in range(9):
                if i != x and board[i][y] == board[x][y]:
                    return False

            for j in range(9):
                if j != y and board[x][j] == board[x][y]:
                    return False

            i = 3 * (x // 3)
            while i < 3 * (x // 3 + 1):
                j = 3 * (y // 3)
                while j < 3 * (y // 3 + 1):
                    if (i != x or j != y) and board[i][j] == board[x][y]:
                        return False
                    j += 1
                i += 1
            return True

        def solver(board):
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if(board[i][j] == '.'):
                        for k in range(9):
                            board[i][j] = chr(ord('1') + k)
                            if isValid(board, i, j) and solver(board):
                                return True
                            board[i][j] = '.'
                        return False
            return True

        solver(board)

[4]:

s = Solution1()
board = [
    ['5', '3', '.', '.', '7', '.', '.', '.', '.'],
    ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
    ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
    ['8', '.', '.', '.', '6', '.', '.', '.', '3'],
    ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
    ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
    ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
    ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
    ['.', '.', '.', '.', '8', '.', '.', '7', '9'],
]
s.solveSudoku(board)
# for i in range(len(board)):
#     print(board[i])
# ['5', '3', '4', '6', '7', '8', '9', '1', '2']
# ['6', '7', '2', '1', '9', '5', '3', '4', '8']
# ['1', '9', '8', '3', '4', '2', '5', '6', '7']
# ['8', '5', '9', '7', '6', '1', '4', '2', '3']
# ['4', '2', '6', '8', '5', '3', '7', '9', '1']
# ['7', '1', '3', '9', '2', '4', '8', '5', '6']
# ['9', '6', '1', '5', '3', '7', '2', '8', '4']
# ['2', '8', '7', '4', '1', '9', '6', '3', '5']
# ['3', '4', '5', '2', '8', '6', '1', '7', '9']
assert board[0] == ['5', '3', '4', '6', '7', '8', '9', '1', '2']
assert board[1] == ['6', '7', '2', '1', '9', '5', '3', '4', '8']
assert board[2] == ['1', '9', '8', '3', '4', '2', '5', '6', '7']
assert board[3] == ['8', '5', '9', '7', '6', '1', '4', '2', '3']
assert board[4] == ['4', '2', '6', '8', '5', '3', '7', '9', '1']
assert board[5] == ['7', '1', '3', '9', '2', '4', '8', '5', '6']
assert board[6] == ['9', '6', '1', '5', '3', '7', '2', '8', '4']
assert board[7] == ['2', '8', '7', '4', '1', '9', '6', '3', '5']
assert board[8] == ['3', '4', '5', '2', '8', '6', '1', '7', '9']